//https://leetcode.cn/problems/valid-parentheses/?envType=study-plan-v2&envId=top-100-liked
//有效的括号；
//Solution1:java:https://zhuanlan.zhihu.com/p/421186993
//Solution2:C++:https://blog.csdn.net/sandalphon4869/article/details/97547137
//Solution3:C++:官网解法


#include <vector>
#include <stack>
#include <list>
#include <map>
#include <string>
#include <unordered_map>

using namespace std;

class Solution1 {
public:
     bool isValid(string s) {
        int length = s.length();
        if (length % 2 != 0) {
            return false;
        }
        stack<char> stack;
        for (int i = 0; i < length; i++) {
            char c = s.at(i);
            if (isLeftBracket(c)) {
                stack.push(c);
            } else {
                if (stack.empty() || stack.top() != getComplement(c)) {
                    return false;
                }
                stack.pop();
            }
        }
        return stack.empty();
    }
    bool isLeftBracket(char c) {
        return c == '(' || c == '[' || c == '{';
    }
    char getComplement(char c) {
        switch (c) {
        case ')':
            return '(';
        case ']':
            return '[';
        case '}':
            return '{';
        default:
            return ' ';
        }
    }
};

class Solution2 {
public:
    bool isValid(string s) {
        stack<char> stack;
        map<char, char> m = {{'}', '{'},
                            {')', '('},
                            {']', '['}};
        int len=static_cast<int>(s.size());
        for(int i=0;i<len;i++){
            if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
                stack.push(s[i]);//将左括号入栈
            }
            else{
                if(stack.empty())return 0;//发现右括号，但栈为空
                else if(m[s[i]] != stack.top())return 0;//栈顶和右括号应该匹配
                else stack.pop();//发现匹配，出栈
            }
        }
        if(stack.empty())return 1;
        else return 0;//遍历完后栈不为空，则不匹配
    }
};

class Solution3 {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};